
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;

public class DNSRA_M1_JAVA {

    public DNSRA_M1_JAVA() {
    }

    /*******************************************************************************
     * check whether two string is identical
     *If yes, return true, else return false
     *******************************************************************************/
    public boolean Is_Stri_Identi(String strA, String strB) {
        //System.out.println("testB1-----'"+strA+"--------"+strB);
        boolean is_identical = true;
        int lenA = strA.length();
        int lenB = strB.length();
        if (lenA != lenB) {
            is_identical = false;
        }

        if (is_identical) {
            for (int i = 0; i < lenA; i++) {
                if (strA.charAt(i) != strB.charAt(i)) {
                    is_identical = false;
                    break;
                }
            }
        }
        return is_identical;
    }

    /*******************************************************************************
     * Levenshtein Distance Algorithm Implementation
     * Adapted from http://en.wikipedia.org/wiki/Levenshtein_distance
     * Return Levenshtein Distance (edit distance) between strA and strB.
     *******************************************************************************/
    public int calc_edit_dist(String strA, String strB) {
        int lenA = strA.length();
        int lenB = strB.length();
        int[][] m = new int[lenA + 1][lenB + 1];

        for (int i = 0; i < lenA + 1; i++) {
            m[i][0] = i;
        }

        for (int j = 0; j < lenB + 1; j++) {
            m[0][j] = j;
        }

        // remaining points
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (strA.charAt(i - 1) == strB.charAt(j - 1)) {
                    m[i][j] = m[i - 1][j - 1];
                } else {
                    int min = m[i - 1][j - 1] + 1; // substitution
                    int temp = m[i - 1][j] + 1; // deletion
                    if (min > temp) {
                        min = temp;
                    }
                    int temp2 = m[i][j - 1] + 1; // insertion
                    if (min > temp2) {
                        min = temp2;
                    }
                    m[i][j] = min;
                }
            }
        }
        return m[lenA][lenB];
    }

    /*******************************************************************************
     * Read the strings from input file and store the data in a hashmap
     * convert hashmap to 2 dimentional arraylist
     *******************************************************************************/
    public ArrayList<ReadString> ReadFile(File inputFile) throws Exception {
        ArrayList<ReadString> ReadsArrayList = new ArrayList<ReadString>();

        int d = 0;
        int w = 0;
        int l = 0;
        int n = 0;
        String fName;
        String parameters = null;
        //ArrayList<Read> reads = new ArrayList<Read>();

        // Open the file that is the first
        // command line parameter
        fName = inputFile.getName();
        FileInputStream fstream = new FileInputStream(inputFile);

        // Get the object of DataInputStream
        DataInputStream in = new DataInputStream(fstream);
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        String strLine;
        // Read File Line By Line
        for (int i = 1; i <= 8; i++) {
            strLine = br.readLine();
            switch (i) {
                case 3:
                    parameters = strLine.substring(strLine.indexOf(":") + 2);
                    break;
                case 5:
                    d = Integer.parseInt(strLine.substring(strLine.indexOf("=") + 1));
                    break;
                case 6:
                    w = Integer.parseInt(strLine.substring(strLine.indexOf("=") + 1));
                    break;
                case 7:
                    l = Integer.parseInt(strLine.substring(strLine.indexOf("=") + 1));
                    break;
                case 8:
                    n = Integer.parseInt(strLine.substring(strLine.indexOf("=") + 1));
                    break;
                default:
                    break;
            }
        }

        HashMap<String, Integer> ReadsStringValues = new HashMap<String, Integer>();

        // Read the read contents
        for (int i = 1; i <= n; i++) {
            // read_i_1
            strLine = br.readLine();
            strLine = br.readLine();
            if (ReadsStringValues.containsKey(strLine)) {
                int value = (Integer) ReadsStringValues.get(strLine);
                value++;
                ReadsStringValues.remove(strLine);
                ReadsStringValues.put(strLine, value);
            } else {
                ReadsStringValues.put(strLine, 1);
            }
        }

        // Close the input stream
        in.close();

        java.util.Iterator it = ReadsStringValues.entrySet().iterator();
        while (it.hasNext()) {
            java.util.Map.Entry entry = (java.util.Map.Entry) it.next();
            //System.out.println("hash table line"+entry.getKey()+(Integer)entry.getValue());
            ReadString aread = new ReadString("" + entry.getKey(), (Integer) entry.getValue());
            ReadsArrayList.add(aread);
            //System.out.println(entry.getValue());
        }

        return ReadsArrayList;
    }

    /*******************************************************************************
     * Write output file according to the predefined formatted header
     * together with entries from resulting contig array
     *******************************************************************************/
    public void WriteOutputToFile(String fileName, long runningTime, ArrayList<String> arraylist) throws IOException {
        String newFileName = fileName.replaceAll("reads", "contigs");
        PrintWriter writer = new PrintWriter(new FileWriter("../OutputFiles/" + newFileName));
        writer.println("## CS5206 DNSRA project output file");
        writer.println("## Contigus generated from " + fileName + " using Greedy algorithm");
        writer.println("## Algorithm parameters are: 100 10 50 30 0 1");

        DateFormat dateFormat = new SimpleDateFormat("EEE MMM dd HH:mm:ss z yyyy");
        Date date = new Date();
        writer.println("## File generated on: " + dateFormat.format(date));
        writer.println("#\\f=" + fileName);
        writer.println("#\\t=02");
        writer.println("#\\m=" + arraylist.size());
        writer.println("#\\r=" + runningTime);

        for (int i = 0; i < arraylist.size(); i++) {
            writer.println(">contig_" + (i + 1));
            writer.println(arraylist.get(i));
        }
        writer.close();
    }

    /*******************************************************************************
     * Define Arraylist Sort Method
     *******************************************************************************/
    public void ArraySort(ArrayList<ReadString> arraylist) {
        Collections.sort(arraylist, new Comparator<ReadString>() {

            public int compare(ReadString arg0, ReadString arg1) {
                return arg1.Number.compareTo(arg0.Number);
            }
        });

    }

    /*******************************************************************************
     * implement greedy algorithm
     * Inputs:
     * input_file_name: from which gene sequence fragments (reads) are pulled into.
     * _overlap       : define overlap distance in calculating edit distance
     *                postfix-length of current contig and prefix-length of
     *                chosen read or prefix-length of current contig and postfix-length of
     *                chosen read
     * _max_allow_ed  : parameter that define maximum allowable edit distance
     *                in deciding "best" extensibility of current fragments to
     *                the contig.
     * Outputs:       Return an array of resulting contig.
     *******************************************************************************/
    public ArrayList<String> greedy_sequencer_B2(ArrayList<ReadString> arraylist, int _overlap, int _max_allow_ed) {

        int overlap = _overlap; //to check edit distance
        int max_allow_ed = _max_allow_ed;

        ArrayList<String> contig_arr = new ArrayList<String>();// for storing resulting contig
        String cur_contig = "";
        int klen = 0;
        while (true) {
            //add some judge condition ----add by JX
            if (cur_contig.length() == 0) {
                cur_contig = cur_contig + arraylist.get(0).ReadString;
                //System.out.println("Best quality"+arraylist.get(0).ReadString);
                arraylist.get(0).Number -= 1;
                //delete [key,value] after the value become 0
                if (arraylist.get(0).Number == 0) {
                    arraylist.remove(0);
                    if (arraylist.isEmpty()) {
                        System.out.println();
                        System.out.println("contig@: " + cur_contig);
                        contig_arr.add(cur_contig);
                        break;
                    }
                }
            }

            // Two parameters for storing minimum data
            ReadString min_kv = new ReadString("", 0);
            int min_ed = overlap;
            // add extend direction, left for extend the prefix of current contig, right for extend the suffix of current contig----add by JX
            String directiontoextend = "left";

            // Get minimum edit distance to the contig among all string

            for (int i = 0; i < arraylist.size(); i++) {
                // find the "best" string
                String k = arraylist.get(i).ReadString;
                //System.out.println("KKKKKKKKKK:::"+k);
                int v = arraylist.get(i).Number;
                int clen = cur_contig.length();
                klen = k.length();
                int edit_dist_left = calc_edit_dist(cur_contig.substring(0, overlap), k.substring(klen - overlap, klen));
                int edit_dist_right = calc_edit_dist(cur_contig.substring(clen - overlap, clen), k.substring(0, overlap));

                //System.out.println("cur_contig."+cur_contig);
                //System.out.println("k."+k);
                //System.out.println("left_dis........."+edit_dist_left);
                //System.out.println("right_dis........."+edit_dist_right);

                if ((edit_dist_right < min_ed) && (edit_dist_right < edit_dist_left)) {
                    min_ed = edit_dist_right;
                    min_kv = arraylist.get(i);
                    directiontoextend = "right";
                } else if ((edit_dist_left < min_ed) && (edit_dist_left <= edit_dist_right)) {
                    min_ed = edit_dist_left;
                    min_kv = arraylist.get(i);
                    directiontoextend = "left";
                }
                if (min_ed == 0) //# edit distance cannot be lower than 0
                {
                    break;
                }
            }

            //System.out.println("min_ed"+min_ed);

            if (min_ed <= max_allow_ed) {
                klen = min_kv.ReadString.length();
                //System.out.println("KKKKKKKKKKKKK"+klen);
                int val_b4_dec = -1;
                if (directiontoextend.equals("right")) {
                    // cut out the prefix before appending
                    //System.out.println("beforeoooooooooo"+cur_contig);
                    cur_contig = cur_contig + min_kv.ReadString.substring(overlap, klen);
                    //System.out.println("afteroooooooooo"+cur_contig);
                    val_b4_dec = min_kv.Number;
                    min_kv.Number -= 1;
                } else if (directiontoextend.equals("left")) {
                    // cut out the suffix before appending
                    String temp = min_kv.ReadString.substring(0, klen - overlap);
                    //System.out.println("oooooooooo"+min_kv.ReadString+klen + overlap);
                    cur_contig = temp + cur_contig;
                    val_b4_dec = min_kv.Number;
                    //System.out.println("oooooooooo"+min_kv.ReadString);
                    min_kv.Number -= 1;
                }
                //add code to judge whether needed to delete element from array kv_arr ----add by JX
                if (val_b4_dec == 1) {
                    arraylist.remove(min_kv);
                    if (arraylist.isEmpty()) {
                        System.out.println(cur_contig);
                        contig_arr.add(cur_contig);
                        break;
                    }
                }

                System.out.print("."); // To communicate progress feedback
            } else {
                System.out.println();
                System.out.println("*contig: " + cur_contig);
                contig_arr.add(cur_contig);
                cur_contig = "";
                //sorted by value in descending order
                //comment the following line will change the dynamic "best quality" to be static one----add by JX
                //kv_arr = kv_arr.sort{|x,y| y[1]<=>x[1]}
            }
        }//end while
        return contig_arr;
    }

    /*******************************************************************************
     * implement greedy algorithm use the method of B1
     *******************************************************************************/
    public ArrayList<String> greedy_sequencer_B1(ArrayList<ReadString> arraylist, int accepted_smallest_overlap, int accepted_largest_overlap) {

        int small_overlap = accepted_smallest_overlap;
        int large_overlap = accepted_largest_overlap;


        ArrayList<String> contig_arr = new ArrayList<String>();// for storing resulting contig
        String cur_contig = "";
        int klen = 0;
        while (true) {
            //add some judge condition ----add by JX
            if (cur_contig.length() == 0) {
                cur_contig = cur_contig + arraylist.get(0).ReadString;
                //System.out.println("Best quality"+arraylist.get(0).ReadString);
                arraylist.get(0).Number -= 1;
                //delete [key,value] after the value become 0
                if (arraylist.get(0).Number == 0) {
                    arraylist.remove(0);
                    if (arraylist.isEmpty()) {
                        System.out.println();
                        System.out.println("contig@: " + cur_contig);
                        contig_arr.add(cur_contig);
                        break;
                    }
                }
            }

            // Two parameters for storing minimum data
            ReadString min_kv = new ReadString("", 0);
            int Over_lap = -1;
            // add extend direction, left for extend the prefix of current contig, right for extend the suffix of current contig----add by JX
            String directiontoextend = "left";

            // Get minimum edit distance to the contig among all string

            for (int i = 0; i < arraylist.size(); i++) {
                // find the "best" string
                String k = arraylist.get(i).ReadString;
                //System.out.println("KKKKKKKKKK:::"+k);
                int v = arraylist.get(i).Number;
                int clen = cur_contig.length();
                klen = k.length();

                for (int overlap = accepted_largest_overlap; overlap >= accepted_smallest_overlap; overlap--) {
                    if (overlap <= Over_lap) {
                        break;
                    }
                    boolean Is_string_identical_l = Is_Stri_Identi(cur_contig.substring(0, overlap), k.substring(klen - overlap, klen));
                    boolean Is_string_identical_r = Is_Stri_Identi(cur_contig.substring(clen - overlap, clen), k.substring(0, overlap));
                    if (Is_string_identical_l) {
                        Over_lap = overlap;
                        directiontoextend = "left";
                        min_kv = arraylist.get(i);
                        break;
                    } else if (Is_string_identical_r) {
                        Over_lap = overlap;
                        directiontoextend = "right";
                        min_kv = arraylist.get(i);
                        break;
                    }
                }

                if (Over_lap == accepted_largest_overlap) //# edit distance cannot be lower than 0
                {
                    break;
                }
            }

            //System.out.println("min_ed"+min_ed);

            if (Over_lap != -1) {
                klen = min_kv.ReadString.length();
                //System.out.println("KKKKKKKKKKKKK"+klen);
                int val_b4_dec = -1;
                if (directiontoextend.equals("right")) {
                    // cut out the prefix before appending
                    //System.out.println("beforeoooooooooo"+min_kv.ReadString.substring(Over_lap, klen));
                    cur_contig = cur_contig + min_kv.ReadString.substring(Over_lap, klen);
                    //System.out.println("afteroooooooooo"+cur_contig);
                    val_b4_dec = min_kv.Number;
                    min_kv.Number -= 1;
                } else if (directiontoextend.equals("left")) {
                    // cut out the suffix before appending
                    String temp = min_kv.ReadString.substring(0, klen - Over_lap);
                    //System.out.println("oooooooooo"+temp);
                    cur_contig = temp + cur_contig;
                    val_b4_dec = min_kv.Number;
                    //System.out.println("oooooooooo"+min_kv.ReadString);
                    min_kv.Number -= 1;
                }
                //add code to judge whether needed to delete element from array kv_arr ----add by JX
                if (val_b4_dec == 1) {
                    arraylist.remove(min_kv);
                    if (arraylist.isEmpty()) {
                        System.out.println(cur_contig);
                        contig_arr.add(cur_contig);
                        break;
                    }
                }

                System.out.print("."); // To communicate progress feedback
            } else {
                System.out.println();
                System.out.println("*contig: " + cur_contig);
                contig_arr.add(cur_contig);
                cur_contig = "";
                //sorted by value in descending order
                //comment the following line will change the dynamic "best quality" to be static one----add by JX
                //kv_arr = kv_arr.sort{|x,y| y[1]<=>x[1]}
            }
        }//end while
        return contig_arr;
    }
}
